/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if (root === null) return 0

    let queue = [root], valQueue = [root.val], node, len, nodeVal

    while (queue.length > 0) {
        len = queue.length
        for (let i = 0; i < len; i++) {
            node = queue.shift()
            nodeVal = valQueue.shift()
            if(node.left === null && node.right === null && nodeVal === targetSum){
                return true
            }
            if(node.left){
                queue.push(node.left)
                valQueue.push(nodeVal + node.left.val)
            }
            if(node.right){
                queue.push(node.right)
                valQueue.push(nodeVal + node.right.val)
            }
        }
    }

    return false
};



/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if (root === null) return false
    return getPathSum(root, targetSum, 0)
};


function getPathSum(root, targetSum, sum) {
    sum += root.val
    if (root.left === null && root.right === null && targetSum === sum) {
        return true
    }

    let r1 = false, r2 = false
    if (root.left) {
        r1 = getPathSum(root.left, targetSum, sum)
    }

    if (root.right) {
        r2 = getPathSum(root.right, targetSum, sum)
    }
    return r1 || r2
}
